The importance of error correction coding of data in digital computer systems has increased greatly as the density of the data recorded on mass storage media, for example, magnetic tapes, has increased. With higher recording densities, a tiny imperfection in the recording surface of a tape can corrupt a large amount of data. In order to avoid losing that data, error correction codes ("ECC's") are employed to, as the name implies, correct the erroneous data.
Before a string of data symbols is recorded on a tape, it is mathematically encoded to form ECC symbols. The ECC symbols are then appended to the data string to form code words--data symbols plus ECC symbols--and the code words are then stored on the tape. When the stored data is to be retrieved from the tape, the code words containing the data symbols are retrieved from the tape and mathematically decoded. During decoding any errors in the data are detected and, if possible, corrected through manipulation of the ECC symbols [For a detailed description of decoding see Peterson and Weldon, Error Correction Codes, 2d Edition, MIT Press, 1972].
Stored digital code words can contain multiple errors. One of the most effective types of ECC used for the correction of multiple errors is a Reed-Solomon code [For a detailed description of Reed-Solomon codes, see Peterson and Weldon, Error Correction Codes]. Error detection and correction techniques for Reed-Solomon ECC's are well known. Id.
Data is typically stored on a tape in a long sequence of symbols. Errors in the stored data often occur in long bursts, that is, in a succession of many erroneous symbols. Techniques designed for detecting and/or correcting single or multiple independent errors, which do not ordinarily occur in bursts, are not well suited for the detection or correction of these long burst errors. Thus special error detection and/or correction techniques are typically employed to handle the long burst errors. One such technique is interleaving, which involves encoding into a single code word data symbols which are recorded non-continuously on the tape.
Known tape storage systems which use interleaved encoding start an encoding operation by storing in a data buffer the data symbols to be encoded. The systems then retrieve the data symbols from the data buffers in the order required for ECC encoding, and encode them to generate ECC redundancy symbols. Next, the systems store the generated ECC redundancy symbols in the data buffers along with the data. Finally, the systems retrieve the data and ECC symbols from the data buffers in the order in which they are to be recorded and serially record them on the tapes. The ordered sequence of data symbol buffering, encoding, ECC redundancy symbol buffering and recording operations take a relatively long time to perform in order to arrange the data and generated ECC redundancy symbols for serial recording.
The faster the data can be encoded to form interleaved ECC redundancy symbols, the faster the system can perform recording operations and the more recording operations it can perform in a given amount of time. The effective data transfer rate thus increases as the speed of error correction encoding increases. Accordingly, a mechanism is desirable for quickly interleaving and encoding data symbols using a code which protects them from long burst errors.